// https://www.lintcode.com/problem/partition-array/

class Solution {
public:
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition
     */
    int partitionArray(vector<int> &nums, int k) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high)
        {
            while (nums[low] < k)
            {
                low++;
            }
            while (nums[high] >= k)
            {
                high--;
            }
            if (low <= high)
            {
                int tmp = nums[low];
                nums[low] = nums[high];
                nums[high] = tmp;
                low++;
                high--;
            }
        }
        return low;
    }
};